package com.it.od.od20221203;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author: liminghui
 * @date: 2022/12/3 16:17
 * @version: 1.0
 * @description: 开租户, 求最短时长, 图谱 广度优先搜索，bfs
 * 1、题目描述
 * 当前IT部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套IT服务。
 * 每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为1。部署任务项之间可能存在依赖，假如任务2依赖任务1，那么等任务1部署完，任务2才能部署。
 * 任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。
 * 没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。
 * 给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。
 * 2、输入描述
 * 第一行是任务数taskNum,第二行是任务的依赖关系数relationsNum接下来 relationsNum 行，每行包含两个id，描述一个依赖关系，格式为: Di Dj，
 * 表示部署任务部署完成了，部署任务j才能部署，IDi 和IDj 值的范围为: [0,taskNum)注:输入保证部署任务之间的依赖不会存在环。
 * 输入
 * 5
 * 5
 * 0 4
 * 1 2
 * 1 3
 * 2 3
 * 2 4
 * * 3、输出描述
 * * 1个整数，表示一个站点的最短开站时间。
 * 输出
 * 3
 */
public class Main3 {
    public static void main(String[] args) {
        method1();
    }

    // 每个站点时间一样
    private static void method1() {
        Scanner sc = new Scanner(System.in);
        int taskNum = Integer.parseInt(sc.nextLine());
        int relationsNum = Integer.parseInt(sc.nextLine());
        int[][] relations = new int[relationsNum][2];
        for (int i = 0; i < relationsNum; i++) {
            int[] edge = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            relations[i] = edge;
        }
        //    初始化图邻接表，入度表
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] inDegrees = new int[taskNum];
        for (int[] relation : relations) {
            map.computeIfAbsent(relation[0], key -> new ArrayList<>()).add(relation[1]);
            inDegrees[relation[1]]++;
        }
        // 入度为0的入队，bfs,每个站点时间一样
        int level = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size(); // 记住第level层的元素个数
            level++;
            for (int i = 0; i < size; i++) {
                Integer node = queue.poll();
                List<Integer> childs = map.getOrDefault(node, new ArrayList<>());
                for (Integer child : childs) {
                    inDegrees[child]--;
                    if (inDegrees[child] == 0) {
                        queue.add(child);
                    }
                }
            }
        }
        System.out.println(level);
    }

    // 如果站点时间不一样的话。
    private static void method2() {
        Scanner sc = new Scanner(System.in);
        int taskNum = Integer.parseInt(sc.nextLine());
        int relationsNum = Integer.parseInt(sc.nextLine());
        int[][] relations = new int[relationsNum][2];
        for (int i = 0; i < relationsNum; i++) {
            int[] edge = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            relations[i] = edge;
        }
        //    初始化图邻接表，入度表
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] inDegrees = new int[taskNum];
        for (int[] relation : relations) {
            map.computeIfAbsent(relation[0], key -> new ArrayList<>()).add(relation[1]);
            inDegrees[relation[1]]++;
        }
        // 入度为0的入队，bfs
        int total = 0;
        Queue<Integer[]> queue = new LinkedList<>(); // {[站点id，时间]}
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                total = Math.max(total, 1);
                queue.add(new Integer[]{i, 1});
            }
        }
        while (!queue.isEmpty()) {
            Integer[] node = queue.poll();
            Integer nodeId = node[0];
            Integer time = node[1];
            List<Integer> childs = map.getOrDefault(nodeId, new ArrayList<>());
            for (Integer child : childs) {
                inDegrees[child]--;
                if (inDegrees[child] == 0) {
                    int t = time + 1;
                    total = Math.max(total, t);
                    queue.add(new Integer[]{child, t});
                }
            }
        }
        System.out.println(total);
    }
}
